package huffmanCode;
/*
 * Huffman在线编码解码：https://huffman-coding-online.vercel.app
 * 注意同一字符串的Huffman编码可能不唯一，编码长度唯一 
 */
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class HuffmanNode {
	char c;
	int f;
	HuffmanNode l, r;

	public HuffmanNode(char c, int f) {
		this.c = c;
		this.f = f;
		this.l = null;
		this.r = null;
	}

	public HuffmanNode(char c, int f, HuffmanNode l, HuffmanNode r) {
		this.c = c;
		this.f = f;
		this.l = l;
		this.r = r;
	}

	public boolean isLeaf() {
		return l == null && r == null;
	}
}

public class Main {
	// 字符出现频率
	public static Map<Character, Integer> freq = new HashMap<>();
	// 字符对应huffman编码
	public static Map<Character, String> huffmanCodes = new HashMap<>();
	// huffman树的根
	public static HuffmanNode root = null;

	// 构建Huffman树
	public static HuffmanNode buildHuffmanTree(String text) {
		// 1. 统计字符频率
		for (char c : text.toCharArray()) {
			freq.put(c, freq.getOrDefault(c, 0) + 1);
		}

		// 2. 创建优先队列（最小堆）
		PriorityQueue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>(new Comparator<HuffmanNode>() {
			@Override
			public int compare(HuffmanNode o1, HuffmanNode o2) {
				return o1.f - o2.f;
			}
		});

		// 遍历 map
		for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
			pq.add(new HuffmanNode(entry.getKey(), entry.getValue()));
		}

		// 3. 构建Huffman树
		while (pq.size() > 1) {
			HuffmanNode left = pq.poll();
			HuffmanNode right = pq.poll();
			// 非叶子节点用原字符串不包含的'\0'表示
			HuffmanNode parent = new HuffmanNode('\0', left.f + right.f, left, right);
			pq.add(parent);
		}

		return pq.poll();
	}

	// 生成Huffman编码表
	// 遍历 root 到每个叶子的路径
	public static void generateCodes(HuffmanNode node, String code) {
		if (node == null)
			return;

		if (node.isLeaf()) {
			huffmanCodes.put(node.c, code);
			return;
		}

		generateCodes(node.l, code + "0");
		generateCodes(node.r, code + "1");
	}

	// 编码文本
	public static String encode(String text) {
		if (text == null || text.isEmpty())
			return "";

		// 构建Huffman树
		root = buildHuffmanTree(text);

		// 生成编码表
		generateCodes(root, "");

		// 输出码表
		for (Map.Entry<Character, String> entry : huffmanCodes.entrySet()) {
			System.out.printf("%s,%s\n", entry.getKey(), entry.getValue());
		}

		// 编码文本
		StringBuilder encodedText = new StringBuilder();
		for (char c : text.toCharArray()) {
			encodedText.append(huffmanCodes.get(c));
		}

		return encodedText.toString();
	}

	// 解码文本
	public static String decode(String encodedText, HuffmanNode root) {
		if (encodedText == null || encodedText.isEmpty())
			return "";

		StringBuilder decodedText = new StringBuilder();
		HuffmanNode current = root;

		for (char bit : encodedText.toCharArray()) {
			if (bit == '0') {
				current = current.l;
			} else if (bit == '1') {
				current = current.r;
			}
			// 找到叶子节点，解码字符，还原到root
			if (current.isLeaf()) {
				decodedText.append(current.c);
				current = root;
			}
		}

		return decodedText.toString();
	}

	public static void main(String[] args) {
		String str = "this is an example for huffman encoding";
		// 编码
		String code = encode(str);

		System.out.println(code);
		
		// 解码
		System.out.println(decode(code,root));
	}
}